package Medium.LinkedList;

import Base.ListNode;

/**
 * @author: white-zhou
 * @date: 2024-10-11 18:32
 **/
public class RemoveNthFromEnd {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cur = head;
        int size = 0;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        if (size == 1) {
            return null;
        }
        if (size == n) {
            return head.next;
        }
        ListNode temp = head;
        int index = size - n;
        while (temp != null) {
            index--;
            if (index == 0) {
                temp.next = temp.next.next;
                break;
            }
            temp = temp.next;
        }
        return head;
    }

    // 双指针法
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        // 创建一个虚拟头结点
        ListNode dummy = new ListNode(0, head);
        ListNode fast = head;
        ListNode slow = dummy;

        // 快指针先走n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // 快慢指针同时走，直到快指针走到尾部
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除倒数第n个结点
        slow.next = slow.next.next;

        return dummy.next;
    }
}
